package one.one.twentyNine;

public class Rank {

	static int rank(int[] a, int k, int h, int t) {
		int l = a.length;
		if (k < a[h]) {
			return -1;
		}
		if (k > a[t]) {
			return t - h + 1;
		}
		int mid = h + (t - h) / 2;
		if (k < a[mid]) {
			return rank(a, k, h, mid - 1);
		} else if (k > a[mid]) {
			return rank(a, k, mid + 1, t);
		} else {
			// k=a[mid]
			int i = mid - 1;
			for (i = mid - 1; i >= 0 && a[i] == k; i--) {
			}
			return i + 1;
		}
	}

	static int rank(int[] a, int k) {
		return rank(a, k, 0, a.length - 1);
	}

	static int count(int[] a, int k, int h, int t) {

		if (k < a[h]) {
			return -1;
		}
		if (k > a[t]) {
			return -1;
		}
		int mid = h + (t - h) / 2;
		if (k < a[mid]) {
			return count(a, k, h, mid - 1);
		} else if (k > a[mid]) {
			return count(a, k, mid + 1, t);
		} else {
			// k==a[mid]
			int r = 1;
			for (int i = mid - 1; i >= 0 && a[i] == k; i--) {
				r++;
			}

			for (int j = mid + 1; j <= t && a[j] == k; j++) {
				r++;
			}
			return r;
		}
	}

	static int count(int[] a, int k) {
		return count(a, k, 0, a.length - 1);
	}

	public static void main(String[] args) {
		int[] a = { 0,1,2,3,3,3,4,5,6,7,8 };
		int k = 3;
		int i = rank(a, k);
		int j = count(a, k);
		for(int index=i;index<=i+j-1;index++) {
			System.out.print(" "+a[index]+" ");
		}
	}

}
